package practice_2025_9.practice_9_13;

import practice_2025_9.practice_9_5.ListNode;

import java.util.PriorityQueue;

class Solution {
    public String convert(String s, int numRows) {
        if (numRows == 1) {
            return s;
        }
        StringBuilder stringBuilder = new StringBuilder();
        int d = 2 * numRows - 2;
        for(int i = 0; i < numRows; i++) {
            if (i == 0 || i == numRows - 1) {
                for(int j = i; j < s.length(); j += d) {
                    stringBuilder.append(s.charAt(j));
                }
            } else {
                for(int j = i, k = d - j; j < s.length() || k < s.length(); j += d, k += d) {
                    if (j < s.length()) {
                        stringBuilder.append(s.charAt(j));
                    }
                    if (k < s.length()) {
                        stringBuilder.append(s.charAt(k));
                    }
                }
            }
        }
        return stringBuilder.toString();
    }

    public ListNode sortList(ListNode head) {
        // 将链表按升序排列 -> 小根堆
        PriorityQueue<ListNode> queue = new PriorityQueue<>((v1, v2) -> v1.val - v2.val);
        ListNode cur = head;
        while(cur != null) {
            queue.add(cur);
            cur = cur.next;
        }
        ListNode newHead = new ListNode();
        cur = newHead;
        while(!queue.isEmpty()) {
            ListNode node = queue.poll();
            cur.next = node;
            cur = cur.next;
        }
        cur.next = null;
        return newHead.next;
    }
}